package BitwiseOperation.Easy;

import java.util.LinkedList;

public class LC0338 {
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            ret[i] = oneNumbersInBinary(i);
        }
        return ret;
    }

    private int oneNumbersInBinary(int decimal) {
        LinkedList<Integer> linkedList = decimal2BinaryQueue(decimal);
        int ret = 0;
        for (Integer bit : linkedList) {
            if (bit == 1) ret++;
        }
        return ret;
    }

    /**
     * 十进制转二进制的方法：除二取余，倒序排列
     */
    private LinkedList<Integer> decimal2BinaryQueue(int decimal) {
        int remainder = decimal;
        LinkedList<Integer> queue = new LinkedList<>();
        while (remainder > 0) {
            queue.offer(remainder % 2);
            remainder /= 2;
        }

        return queue;
    }
}
